package com.dzu.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhaoDong
 * @date 2022/7/26 9:24
 * @description 28. 实现 strStr()
 * <p>
 * 示例 1：
 * <p>
 * 输入：haystack = "hello", needle = "ll"
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：haystack = "aaaaa", needle = "bba"
 * 输出：-1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test28 {

    public static void main(String[] args) {
        String s1 = "abcabcabd";
        String s2 = "abcabd";
        int i = strStr3(s1, s2);
        System.out.println(i);
    }

    /**
     * kmp
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr3(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }


    /**
     * 朴素解法
     * 直观的解法的是：枚举原串 ss 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：
     * <p>
     * 匹配成功：返回本次匹配的原串「发起点」。
     * 匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。
     *
     * @param ss
     * @param pp
     * @return
     */
    public int strStr2(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) {
                return i;
            }
        }
        return -1;
    }


    // 滑动窗口
    public static int strStr(String haystack, String needle) {
        List<Character> array1 = new ArrayList<>();
        for (int i = 0; i < needle.length(); i++) {
            char c = needle.charAt(i);
            array1.add(c);
        }

        List<Character> array = new ArrayList<>();


        int start = 0;
        for (int end = 0; end < haystack.length(); end++) {
            char c = haystack.charAt(end);
            array.add(c);

            if (array.equals(array1)) {
                return start;
            }

            if (end - start >= needle.length() - 1) {
                Character key = haystack.charAt(start);
                array.remove(key);
                start++;
            }
        }
        return -1;
    }
}
